package LeetCode;

public class LC_055_JumpGame {
    public static void main(String[] args) {

    }

    static class Solution {
        public boolean canJump(int[] nums) {
            int n = nums.length;
            int dp[] = new int[n];
            dp[0] = nums[0];
            for (int i = 1; i < n; i++) {
                if (i <= dp[i - 1])
                    dp[i] = Math.max(dp[i - 1], i + nums[i]);
                else
                    dp[i] = dp[i - 1];
            }
            return dp[n - 1] >= (n - 1);
        }
    }

    static class Solution_2 {
        public boolean canJump(int[] nums) {
            int n = nums.length;
            int maxJump = 0;
            for (int i = 0; i < n; i++) {
                if (i > maxJump || maxJump >= (n - 1))
                    break;
                maxJump = Math.max(maxJump, i + nums[i]);
            }
            return maxJump >= (n - 1);
        }
    }

}
